The present invention relates to an apparatus for inversely converting and decoding variable-length-coded compressed code sequences.
In recent years, techniques for decoding high-efficiently coded and compressed images are eagerly researched, and used in the fields of computers, communication, broadcasting and the like. In addition, Joint Photographic Coding Experts Group (JPEG) is recommended as an International Standard of compression coding and decompression decoding of these images, and Moving Picture Experts Group 1 (MPEG1) video and Moving Picture Experts Group 2 (MPEG2) Video are recommended as International Standards of moving picture decoding.
According to these methods, image information is divided into blocks each being composed of a predetermined number of pixels. Each pixel included in the block is orthogonally transformed, quantized, and entropy-coded, to generate a code (in these method, a Huffman code is used). Plural generated codes are combined to compose a compressed code sequence (also referred to simply as a code sequence). The compressed code sequence is entropy-decoded, inversely quantized, and inversely-orthogonally transformed, for each code, to generate a restored image.
It should be noted here that the processing of orthogonally transforming, quantizing, and entropy-coding each pixel is hereinafter referred to as compression coding (or referred to simply as coding), and distinguished from the entropy coding. In addition, it should be noted that the processing of entropy-decoding, inversely quantizing, and inversely-orthogonally transforming a code is referred to as decompression decoding (or referred to simply as decoding), and distinguished from the entropy decoding.
Hereinafter, a description is given of a structure of a circuit for compressing/decompressing common images according to a baseline method as a function which is essential to an image encoder/decoder in conformance with the JPEG recommendation. FIG. 2 is a block diagram illustrating the circuit for compressing/decompressing images according to the JPEG baseline method.
This compression/decompression circuit comprises a block transformation unit 201, a DCT unit 202, a quantization unit 203, a Huffman coding unit 204, a marker generation unit 205, a Huffman decoding unit 206, and a marker decryption unit 207. Here, only the descriptions relating to the decompression decoding are given. The compression coding which has no direct bearing on the present invention is not described here. The marker decryption unit 207 decrypts a marker section which is stored at the head of the compressed code sequence, obtains information at the coding of a target image such as the size of the image, a quantization table and an entropy decoding table, and stores the information in a quantization table RAM (not shown) or an entropy decoding table RAM (not shown in FIG. 2).
The Huffman decoding unit 206 entropy-decodes an entropy code section which is stored subsequent to the marker section of the compressed code sequence, and has been subjected to Huffman coding which is a kind of variable length coding and also a kind of entropy coding, in accordance with an entropy decoding table stored in the entropy decoding table RAM, to output a quantization DCT coefficient.
The quantization unit 203 multiplies a corresponding element of a quantization table stored in the quantization table RAM by the quantization DCT coefficient, and outputs a DCT coefficient to carry out the inverse quantization. The DCT unit 202 subjects the DCT coefficient to inverse transformation of DCT (Discrete Cosine Transformation) as a kind of the orthogonal transformation, and outputs pixel data of a block composed of 8 pixels x 8 pixels. The block transformation unit 201 rearranges the pixel data which have been received in block units, to output a restored image. Since the DCT and the quantization are already known techniques, they are not described in detail here. Further, the processed contents of the marker decryption unit 207 and the processed contents in the block transformation unit 201 are also well-known to persons expert in JPEG, and the processing circuit can be easily constructed. Therefore, the detailed descriptions thereof are not given here.
Before describing the remaining Huffman decoding unit 206, a structure of the compressed code sequence of JPEG is described with reference to FIG. 3.
FIG. 3 shows that the compressed code sequence includes a marker section 301 at the head, followed by an entropy code section 302. The entropy code section 302 has a structure in which a Huffman code 303 as a variable length code and an additional bit 304 are alternately repeated. The code length (hereinafter referred to as xe2x80x9cLhxe2x80x9d) of the Huffman code 303 is obtained from the Huffman code 303 itself, while the additional bit 304 is an uncoded binary bit string, and its bit length (hereinafter referred to as xe2x80x9cLaxe2x80x9d) is obtained from the result of the entropy decoding of the Huffman code 303.
Next, the Huffman decoding unit 206 shown in FIG. 2 of the compression/decompression circuit is described with reference to FIG. 14. The Huffman decoding unit 206 comprises a code location unit 2101, a boundary code register 2102, a Huffman code length detection unit 2103, a base address register 2104, an address generation unit 2105, an entropy decoding table RAM 2106, and an additional bit decoding unit 2107.
The code location unit 2101 extracts a 16-bit bit string which is a bit string of the maximum code length (hereinafter referred to as xe2x80x9cLhmaxxe2x80x9d) of the Huffman code from the head of the compressed code sequence, and outputs the 16-bit bit string to the Huffman code length detection unit 2103 and the address generation unit 2105. Further, it extracts a 11-bit bit string which is a bit string of the maximum bit length (hereinafter referred to as xe2x80x9cLamaxxe2x80x9d) of the additional bit from the head of the compressed code sequence, and outputs the 11-bit bit string to the additional bit decoding unit 2107. When the Huffman code length Lh is obtained by the Huffman code length detection unit 2103, the code location unit 2101 carries out a shift operation of the Huffman code length Lh, obtains the next data from the compressed code sequence as required, and locates the additional bit. Further, when the additional bit length La is obtained from the entropy decoding table RAM 2106, the code location unit 2101 carries out the shift operation of the additional bit length La, and obtains the next data from the compressed code sequence as required, and locates the next Huffman code.
Prior to the start of the decompression decoding, the minimum code value for each code length is stored in the boundary code register 2102.
The Huffman code length detection unit 2103 compares the 16-bit bit string obtained by the code location unit 2101 with the contents of the boundary code register 2102, assumes that the Huffman code exists from the head of the bit string obtained by the code location unit 2101, and detects the code length Lh. As described above, in the case of the Huffman code, the code length can be obtained before referring to the decoding table RAM 2106.
Prior to the start of the decompression decoding, a base address which is an address of the entropy decoding table RAM 2106, corresponding to the Huffman code of the minimum code value for each code length is stored in the base address register 2104.
The address generation unit 2105 compares the 16-bit bit string obtained by the code location unit 2101, the Huffman code length Lh obtained by the Huffman code length detection unit 2102 and the contents of the base address register 2104, and generates an address for referring to the entropy decoding table RAM 2106.
Prior to the start of the decompression decoding, the bit length of an additional bit corresponding to each codeword is stored in the entropy decoding table RAM 2106.
The additional bit decoding unit 2107 extracts a bit string of the additional bit length La obtained from the entropy decoding table RAM 2106, from the head of the 11-bit bit string obtained by the code location unit 2101, and outputs the extracted bit string as a quantization DCT coefficient.
FIG. 15 is a diagram showing the relationship between the boundary code register 2102 and the Huffman code length detection unit 2103. The boundary code register 2102 is a register file which is constituted by plural registers, i.e., a register 2201-1 for containing a boundary code of an 1-bit length Huffman code, a register 2201-2 for containing a boundary code of a 2-bit length Huffman code, . . . , and a register 2201-16 for containing a boundary code of a 16-bit length Huffman code. Prior to the start of the decompression decoding, the minimum code values for the respective code lengths are stored in the boundary code register 2102 as the boundary codes.
The Huffman code length detection unit 2103 comprises a 1-bit size comparator 2202-1, 2- bit size comparator 2202-2, . . . , 16-bit size comparator 2202-16, a priority encoder 2203, and a selector 2204. The Huffman code length detection unit 2103 compares 1 bit from the head of an input bit string with the boundary code stored in the register 2201-1 of the boundary code register 2102, which contains the boundary code of 1-bit length, by means of the size comparator 2202-1. Similarly, the Huffman code length detection unit compares 2 bits from the head of the input bit string with the boundary code stored in the register 2202-2 which contains the boundary code of 2-bit length, by means of the size comparator 2202-2. This is performed up to 16 bits which are the maximum code length of the Huffman code.
From the 16 results of the size comparison, the priority encoder 2203 outputs the minimum of the code lengths for which the bit string of the boundary code is shorter, as the Huffman code length Lh.
The selector 2204 selects the boundary code of the code length output from the priority encoder 2203, which is indicated by the Huffman code length Lh, from the boundary code register 2102, and outputs the same as the boundary code.
FIG. 16 is a diagram showing the relationship between the base address register 2104 and the address generation unit 2105. The base address register 2104 is a register file constituted by plural registers, which contains addresses of the entropy decoding table RAM 2106. The base address register 2104 is constituted by a register 2301-1 for containing an address corresponding to a Huffman code which is the minimum value among 1-bit length Huffman codes, a register 2301-2 for containing an address corresponding to a Huffman code which is the minimum value among 2-bit length Huffman codes, . . . , and a register 2301-16 for containing an address corresponding to a Huffman code which is the minimum value among 16-bit length Huffman codes. Prior to the start of the decompression decoding, the address of the entropy decoding table RAM 2106 corresponding to the Huffman code of the minimum code value for each code length is stored in the base address register 2104 as the base address.
The address generation unit 2105 comprises a selector 2302, a selector 2303, an adder 2304 and an adder 2305.
The selector 2302 selects a base address corresponding to the input Huffman code length Lh from the base addresses stored in the base address register 2140, and outputs the selected base address to the adder 2305. The selector 2303 selects a bit string from the head of a bit string which is a part of the input compressed code sequence so that bits of the input Huffman code length Lh become effective bits, and outputs the selected bit string to the adder 2304.
The adder 2304 subtracts the input boundary code from the bit string input from the selector 2303, and output the results to the adder 2305. The adder 2305 adds the value input from the adder 2304 and the value input from the selector 2302, and output the result as the address.
The operation of the above-mentioned conventional Huffman decoding unit is described with reference to a timing chart shown in FIG. 17. Initially, the code location unit 2101 reads first data of the entropy code section and outputs the maximum code length Lhmax of the Huffman code, i.e., =16 bits, from the first bit (2401).
Next, the Huffman code length detection unit 2103 obtains the Huffman code length Lh (2402). When the Huffman code length Lh is obtained, the address generation unit 2105 obtains an address to be referred to in the entropy decoding table RAM 2106 (2403). The Huffman code length detection (2402) and the address generation (2403) are carried out in one cycle.
Simultaneously, the obtained address is given to the entropy decoding table RAM 2106 (2404). Currently, the speed of the logical circuit has been increased with advances in the semiconductor process technology, but the speed of the RAM is still lower than that of the logical circuit. Therefore, it takes one cycles to give the address to the entropy decoding table RAM 2106, and one cycle to wait for output of data. The additional bit length La is obtained from the entropy decoding table RAM 2106 (2405).
Then, the code location unit 2101 performs the shift operation of the obtained additional bit length La, and locates the second Huffman code (2401). Simultaneously, the additional bit decoding unit 2107 extracts a bit string of the obtained additional bit length La from the head of the bit string which has been given by the code location unit 2101, to obtain a quantization DCT coefficient.
In order to decode the following second or later Huffman code and additional bit, the decoding process is continued from the Huffman code length detection (2402) and the address generation (2403). As can be seen in FIG. 17, the prior art Huffman decoding unit can output the quantization DCT coefficient once every four cycles.
As described above, the compressed code sequence is decompressed and decoded to obtain the restored image. However, the process of the compression coding or decompression decoding for images requires a considerably large operation amount, and it takes much time even when the special circuit shown in the above-mentioned prior art compression/decompression circuit is employed. Further, in recent years, there is a tendency that the definition in images is increased more, and a longer processing time is required.
In digital electronic circuits, in order to solve the problems in the processing time, it is common to realize speeding-up by parallelization of the circuits or the pipeline process. However, in the case of a processing including a feedback loop like decoding of variable length codes, only after the processing of one Huffman code has been finished, the decoding start position of the next Huffman code is known. Therefore, the speeding-up by the parallelization of the circuits or the pipeline processing cannot be enabled, and this causes the bottle neck in the improvement of the processing speed.
It is an object of the present invention to enable a pipeline processing in a variable length code decoding circuit, and improve the performance in the decompression decoding process time of the compression/decompression circuit.
Other objects and advantages of the present invention will become apparent from the detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the spirit and scope of the invention will be apparent to those of skill in the art from the detailed description.
A decoder according to a 1st aspect of the present invention for decoding successive first and second variable length codes, with referring to a table which contains a relationship between variable length codes and decoded values comprises: a code location unit for cutting out plural bit strings from plural different relative positions with respect to a reference position; plural address candidate generation units each generating an address candidate to refer to the table for each of the plural cutout bit strings; a table reference unit for referring to the table to get decoded values on the basis of the generated address candidates; and a control unit for operating the table reference unit for the first variable length code, while simultaneously operating the address candidate generation units for the second variable length code. Therefore, while waiting for output of a decoded value from the table to decode one variable length code, table addresses for the next variable length code can be obtained by the plural address candidates generation units, whereby the pipeline processing of the decoding of the variable length codes is enabled, and the processing time can be reduced as compared to the prior art Huffman decoding unit.
According to a 2nd aspect of the present invention, the decoder of the 1st aspect comprises: a code length calculation unit for obtaining a code length of the input variable length code on the basis of a result of the table reference; and the table reference unit selects a predetermined address from the plural table reference address candidates on the basis of the obtained code length. Therefore, the location of the second variable length code can be easily performed with referring to the code length of the first variable length code.
According to a 3rd aspect of the present invention, in the decoder of the 1st aspect, the number of the address candidate generation units is less than the number of possible kinds of variable length code, and the code location unit outputs a bit string to the address candidate generation units, respectively, with successively shifting the reference position. Therefore, while waiting for output of the decoded value from the table to decode one variable length code, table addresses for the next variable length code can be obtained by the plural address candidate generation units, whereby the pipeline processing of the decoding of variable length codes is enabled. Accordingly, the processing time is reduced as compared to the prior art Huffman decoding unit, as well as the Huffman decoding unit can be realized in a smaller apparatus scale.
According to a 4the aspect of the present invention, in the decoder of the 1st aspect, the variable length code is composed of an additional bit and a secondary variable length code which is obtained by coding at least a bit length of the additional bit, and the number of the address candidate generation units is equal to the number of possible kinds of bit length of the additional bit. Therefore, while waiting for output of a decoded value from the table to decode one variable length code, table addresses for the next variable length code can be obtained by the plural address candidate generation units, whereby the pipeline processing of the decoding of variable length codes is enabled. Accordingly, the pipeline processing of the decoding of variable length codes is enabled, and the processing time is reduced as compared to the prior art Huffman decoding unit, as well as the Huffman decoding unit can be realized in a smaller apparatus scale.
According to a 5th aspect of the present invention, in the decoder of the 4the aspect, the number of the address candidate generation units is less than the number of possible kinds of bit length of the additional bit, and the code location unit outputs a bit string to the address candidate generation units, respectively, with successively shifting the reference position. Therefore, while waiting for output of a decoded value from the table to decode one variable length code, table addresses for the next variable length code can be obtained by the plural address candidates generation units, whereby the pipeline processing of the decoding of variable length codes is enabled. Accordingly, the processing time is reduced as compared to the prior art Huffman decoding unit, as well as the Huffman decoding unit can be realized in a smaller apparatus scale.
According to a 6th aspect of the present invention, the decoder of the 1st aspect comprises a decoding subunit for outputting at least a code length of a variable length code having a predetermined code length or shorter, for that variable length code. Therefore, not only the processing time is reduced as compared to the prior art Huffman decoding unit, but also the processing time can be further reduced.
A decoding method according to a 7th aspect of the present invention for decoding successive first and second variable length codes, with referring to a table which contains a relationship between variable length codes and decoded values comprises a step of simultaneously carrying out a process for referring to the table to get a decoded value for the first variable length code, and a process for generating plural table address candidates to refer to the table for the second variable length code, in parallel. Therefore, while waiting for output of a decoded value from the table to decode one variable length code, table addresses for the next variable length code can be obtained by the plural address candidates generation units, whereby the pipeline processing of the decoding of variable length codes is enabled. Accordingly, the processing time is reduced as compared to the prior art Huffman decoding unit.
According to an 8th aspect of the present invention, the decoding method of the 7th aspect comprises a step of: selecting one address from the plural table address candidates on the basis of a code length of the first variable length code obtained from a result of the table reference for the first variable length code, to locate the second variable length code. Therefore, the location of the second variable length code can be easily performed with referring to the code length of the first variable length code.